/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-06-27
 * Time: 13:04
 */
public class Solution2 {
    //方法二：使用递归的方法，如果当前节点值等于其中一个目标值，那么最近公共祖先就是其中一个
    //如果两个目标值都在左子树那么最近公共祖先就是在左子树，右子树也是一样的情况
    //如果目标值一个在左子树一个在右子树那么root(指的当前的节点)就是最近公共祖先
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        if(root==null){
            return -1;
        }
        //当前节点值等于目标值，那么说明找到了，返回去
        if(root.val==o1 || root.val==o2){
            return root.val;
        }
        //在左子树找目标值
        int leftVal=lowestCommonAncestor( root.left,o1,o2 );
        //在右子树找目标值
        int rightVal=lowestCommonAncestor( root.right,o1,o2 );
        //左子树找不到
        if(leftVal==-1){
            return rightVal;
        }
        //右子树找不到
        if(rightVal==-1){
            return leftVal;
        }
        //都找到了，那么最近公共祖先就是就是root
        return root.val;
    }
}
